/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._77;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 示例:
 *
 * 输入: n = 4, k = 2
 * 输出:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._77
 * @ClassName: Combinations
 * @Author: linyaonan
 * @Date: 2020/1/21 17:01
 */
public class Combinations {
    List<Integer> data;
    List<List<Integer>> result;
    int count;
    public List<List<Integer>> combine(int n, int k) {
        data = new ArrayList<>();
        result = new ArrayList<>();
        if (k > n) {
            return result;
        }
        for (int i = 1; i <= n; i++) {
            data.add(i);
        }

        count = k;
        ArrayList<Integer> add = new ArrayList<>();
        backTracing(0, add);
        return result;
    }

    private void backTracing(int start, List<Integer> add) {
        if (add.size() == count) {
            List<Integer> temp = new ArrayList<>();
            temp.addAll(add);
            result.add(temp);
            return;
        }

        for (int i = start; i < data.size(); i++) {
            add.add(data.get(i));
            // 递归
            backTracing(++start, add);
            // 回溯，index是一直往后推进的
            add.remove(add.size() - 1);
        }
    }
}
